import sys

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxGlobal = -sys.maxsize
        maxSoFar = 0
        for num in nums:
            if maxSoFar <= 0:
                maxSoFar = num
            else:
                maxSoFar += num
            maxGlobal = max(maxGlobal, maxSoFar)
        return maxGlobal

print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))